Video completion refers to a process of filling in missing pixels or replacing pixels in a video. Video completion can be used, for example, to restore damaged or vintage videos, restore corrupted internet video streams (e.g., due to packet drops), remove unwanted objects in post video production editing operations, and/or so on. Existing video completion techniques typically treat a video data sequence as a set of independent 2D image frames to try to locate temporal color/intensity transitions across respective ones of the 2D frames. However, temporal consistency of filled-in (i.e., present or non-missing) portions of a video data sequence cannot be guaranteed. For instance, periodic color transitions in a video stream are often imperceptible or absent.